#pragma once

#include <cassert>
#include <vector>
#include <type_traits>

namespace Transfer
{
    template<typename T>
    class const_array_iterator;

    template<typename T>
    class array_iterator;

    template<typename T>
    class base_array_iterator;

    template<typename T>
    struct _array_op
    {
        static void construct(T* p, const T& val)
        {
            if constexpr(std::is_trivial<T>::value)
                *p = val;
            else
                new(p) T(val);       
        }

        static void construct(T* p, const T&& val)
        {
            if constexpr(std::is_trivial<T>::value)
                *p = val;
            else
                new(p) T(val);       
        }

        static void destruct(T* p)
        {
            if constexpr(!std::is_trivially_destructible<T>::value)
                p->~T();
        }
    };
    
    /*
    高效环形数组，填满后最后 push 的元素会挤出头部的元素。
    GCC9.0编译器 Linux X64平台测试结果:
    push操作
        比std::deque快 1 倍
        比std::list快 2 倍
        比vector根据数组元素的多少快若干数量级
    随机访问
        与vector/deque相当
    */
    template<typename T>
    class CycleArray
    {
        T* _elements;
        ptrdiff_t _front;
        ptrdiff_t _end;
        ptrdiff_t _capacity;
        ptrdiff_t _count;
    public:
        typedef const_array_iterator<T> const_iterator;
        typedef array_iterator<T> iterator;
    public:
        CycleArray(size_t capacity = 20)
        :_capacity(capacity + 1)
        {
            assert(capacity > 2);
            
            _elements = (T*)new char[_capacity * sizeof(T)];
            _front = 0;
            _end = 0;
            _count = 0;
        }

        ~CycleArray()
        {
            if constexpr(!std::is_trivially_destructible<T>::value)
            {
                while (_count > 0)
                {
                    (_elements + _front)->~T();
                    if (++_front == _capacity) _front = 0;
                    --_count;
                }
            }
            else
            {
                _count = 0;
            }
            
            
            delete[] (char*)_elements;
            _elements = nullptr;
            _front = 0;
            _end = 0;
            _capacity = 0;
        }

        CycleArray(CycleArray<T>&& other)
        {
            _capacity = other._capacity;
            _count = other._count;
            _elements = other._elements;
            _front = other._front;
            _end = other._end;

            other._count = 0;
            other._elements = nullptr;
            other._capacity = 0;
            other._front = 0;
            other._end = 0;
        }

        CycleArray(const CycleArray<T>& other)
        {
            CopyFrom(other);
        }

        const CycleArray& operator=(const CycleArray<T>& other)
        {
            if (this != &other)
            {
                this->~CycleArray();
                CopyFrom(other);
            }
            return *this;
        }

        void push(const T& element)
        {
            if (_count == _capacity - 1)
            {
                _array_op<T>::destruct(_elements + _front);
                if (++_front == _capacity) _front = 0;

                _array_op<T>::construct(_elements + _end, element);
                if (++_end == _capacity) _end = 0;
            }
            else
            {
                ++_count;

                _array_op<T>::construct(_elements + _end, element);
                if (++_end == _capacity) _end = 0;
            }            
        }

        void push(T&& element)
        {
            if (_count == _capacity - 1)
            {
                _array_op<T>::destruct(_elements + _front);
                if (++_front == _capacity) _front = 0;

                _array_op<T>::construct(_elements + _end, element);
                if (++_end == _capacity) _end = 0;
            }
            else
            {
                ++_count;

                _array_op<T>::construct(_elements + _end, element);
                if (++_end == _capacity) _end = 0;
            }            
        }

        size_t size() const
        {
            return _count;
        }

        T& operator[](ptrdiff_t i)
        {
            assert(i < _count);
            i += _front;
            if (i >= _capacity) i -= _capacity;
            return _elements[i];
        }

        const T& operator[](ptrdiff_t i) const
        {
            assert(i < _count);
            i += _front;
            if (i >= _capacity) i -= _capacity;
            return _elements[i];
        }

        const T& front() const
        {
            return _elements[_front];
        }

        T& front()
        {
            return _elements[_front];
        }

        const T& back() const
        {
            auto p = _end - 1;
            if (p < 0) p += _capacity;
            return _elements[p];
        }

        T& back()
        {
            auto p = _end - 1;
            if (p < 0) p += _capacity;
            return _elements[p];
        }

        std::vector<T> to_vector() const
        {
            std::vector<T> v;
            for (auto& i : *this)
            {
                v.push_back(i);
            }
            return v;
        }
    public:
        const_iterator begin() const;
        const_iterator end() const;
        iterator begin();
        iterator end();
    private:
        friend class base_array_iterator<T>;
    private:
        void CopyFrom(const CycleArray<T>& other)
        {
            _capacity = other._capacity;
            _elements = (T*) new char[_capacity * sizeof(T)];            
            _front = other._front;
            _end = other._end;

            auto it = other._front;
            _count = 0;
            while (_count < other._count)
            {
                new(_elements + it) T(*(other._elements + it));
                ++_count;
                if (++it == _capacity) it = 0;
            }
        }    
    };

    template<typename T>
    class base_array_iterator
    {
        CycleArray<T>* _array;
        ptrdiff_t _pos;

    public:
        base_array_iterator(CycleArray<T>& a, ptrdiff_t pos)
        : _array(&a), _pos(pos)
        {
        }

        base_array_iterator() : _array(nullptr), _pos(0)
        {

        }

        base_array_iterator<T> operator++(int)
        {
            auto old = base_array_iterator(*this);
            if (++_pos == _array->_capacity) _pos = 0;
            return old;
        }

        base_array_iterator<T>& operator++()
        {
            if (++_pos == _array->_capacity) _pos = 0;
            return *this;
        }

        base_array_iterator<T> operator--(int)
        {
            auto old = base_array_iterator(*this);
            return --old;
        }

        base_array_iterator<T>& operator--()
        {
            return operator-=(1);
        }

        base_array_iterator<T> operator+(ptrdiff_t n) const
        {
            auto iter = base_array_iterator(*this);
            return iter+=(n);
        }

        base_array_iterator<T>& operator+=(ptrdiff_t n)
        {
            _pos += n;
            if (_pos >= _array->_capacity)
                _pos -= _array->_capacity;
            else if (_pos < 0)
                _pos += _array->_capacity;
            return *this;
        }

        base_array_iterator<T> operator-(ptrdiff_t n) const
        {
            auto iter = base_array_iterator(*this);
            return iter-=(n);
        }

        base_array_iterator<T>& operator-=(ptrdiff_t n)
        {
            return *this += (-n);
        }

        ptrdiff_t operator-(const base_array_iterator<T>& other) const
        {
            assert(this->_array == other._array);
            return this->index() - other.index();
        }

        bool operator < (const base_array_iterator<T>& other) const
        {
            assert(this->_array == other._array);
            return this->index() < other.index();
        }

        ptrdiff_t index() const
        {
            auto i = _pos - _array->_front;
            if (i < 0) i += _array->_capacity;
            return i;
        }

        const T& operator[](ptrdiff_t n) const
        {
            assert(n >=0 && n < _array->_count);
            return *(this->operator+(n));
        }

        T& operator[](ptrdiff_t n)
        {
            assert(n >=0 && n < _array->_count);
            return *(this->operator+(n));
        }

        const T& operator*() const
        {
            return _array->_elements[_pos];
        }

        T& operator*()
        {
            return _array->_elements[_pos];
        }

        const T* operator->() const
        {
            return &_array->_elements[_pos];
        }

        T* operator->()
        {
            return &_array->_elements[_pos];
        }

        bool equalsTo(const base_array_iterator<T>& iterB) const
        {
            return this->_pos == iterB._pos && (this->_array == iterB._array);
        }
    };

    template<typename T>
    class const_array_iterator
    {
        base_array_iterator<T> _base_iterator;
    public:
        typedef T value_type;
        typedef T& reference;
        typedef T* pointer;
        typedef ptrdiff_t difference_type;
        typedef std::input_iterator_tag iterator_category;
    public:
        const_array_iterator()
        {
        }

        const_array_iterator(const base_array_iterator<T>& iter)
        :_base_iterator(iter)
        {

        }

        const_array_iterator<T> operator++(int)
        {
            auto old = const_array_iterator(_base_iterator);
            ++_base_iterator;
            return old;
        }

        const_array_iterator<T>& operator++()
        {
            ++_base_iterator;
            return *this;
        }

        const_array_iterator<T> operator--(int)
        {
            auto old = const_array_iterator(_base_iterator);
            --_base_iterator;
            return old;
        }

        const_array_iterator<T>& operator--()
        {
            --_base_iterator;
            return *this;
        }

        const_array_iterator<T> operator+(ptrdiff_t n) const
        {
            return const_array_iterator<T>(_base_iterator + n);
        }

        const_array_iterator<T>& operator+=(ptrdiff_t n)
        {
            _base_iterator += n;
            return *this;
        }

        const_array_iterator<T> operator-(ptrdiff_t n) const
        {
            return const_array_iterator<T>(_base_iterator - n);
        }

        const_array_iterator<T>& operator-=(ptrdiff_t n)
        {
            _base_iterator -= n;
            return *this;
        }

        ptrdiff_t operator-(const const_array_iterator<T>& other) const
        {
            return _base_iterator - other._base_iterator;
        }

        bool operator<(const const_array_iterator<T>& other) const
        {
            return _base_iterator < other._base_iterator;
        }

        const T& operator[](ptrdiff_t n) const
        {
            return _base_iterator[n];
        }

        const T& operator*() const
        {
            return *_base_iterator;
        }

        const T* operator->() const
        {
            return _base_iterator.operator->();
        }

        bool equalsTo(const const_array_iterator<T>& iterB) const
        {
            return this->_base_iterator.equalsTo(iterB._base_iterator);
        }
    };

    template<typename T>
    bool operator == (
            const const_array_iterator<T>& iterA,
            const const_array_iterator<T>& iterB)
    {
        return iterA.equalsTo(iterB);
    }

    template<typename T>
    bool operator != (
            const const_array_iterator<T>& iterA,
            const const_array_iterator<T>& iterB)
    {
        return !iterA.equalsTo(iterB);
    }

    template<typename T>
    class array_iterator
    {
        base_array_iterator<T> _base_iterator;
    public:
        typedef T value_type;
        typedef T& reference;
        typedef T* pointer;
        typedef ptrdiff_t difference_type;
        typedef std::random_access_iterator_tag iterator_category;
    public:
        array_iterator()
        {

        }

        array_iterator(const base_array_iterator<T>& iter)
        : _base_iterator(iter)
        {

        }

        array_iterator<T> operator++(int)
        {
            auto old = array_iterator(_base_iterator);
            ++_base_iterator;
            return old;
        }

        array_iterator<T>& operator++()
        {
            ++_base_iterator;
            return *this;
        }

        array_iterator<T> operator--(int)
        {
            auto old = array_iterator(_base_iterator);
            --_base_iterator;
            return old;
        }

        array_iterator<T>& operator--()
        {
            --_base_iterator;
            return *this;
        }

        array_iterator<T> operator+(ptrdiff_t n) const
        {
            return array_iterator<T>(_base_iterator + n);
        }

        array_iterator<T>& operator+=(ptrdiff_t n)
        {
            _base_iterator += n;
            return *this;
        }

        array_iterator<T> operator-(ptrdiff_t n) const
        {
            return array_iterator<T>(_base_iterator - n);
        }

        array_iterator<T>& operator-=(ptrdiff_t n)
        {
            _base_iterator -= n;
            return *this;
        }

        ptrdiff_t operator-(const array_iterator<T>& other) const
        {
            return _base_iterator - other._base_iterator;
        }

        bool operator<(const array_iterator<T>& other) const
        {
            return _base_iterator < other._base_iterator;
        }

        const T& operator[](ptrdiff_t n) const
        {
            return _base_iterator[n];
        }

        T& operator[](ptrdiff_t n)
        {
            return _base_iterator[n];
        }

        const T& operator*() const
        {
            return *_base_iterator;
        }

        T& operator*()
        {
            return *_base_iterator;
        }

        const T* operator->() const
        {
            return _base_iterator.operator->();
        }

        T* operator->()
        {
            return _base_iterator.operator->();
        }

        bool equalsTo(const array_iterator<T>& iterB) const
        {
            return this->_base_iterator.equalsTo(iterB._base_iterator);
        }
    };

    template<typename T>
    bool operator == (
            const array_iterator<T>& iterA,
            const array_iterator<T>& iterB)
    {
        return iterA.equalsTo(iterB);
    }

    template<typename T>
    bool operator != (
            const array_iterator<T>& iterA,
            const array_iterator<T>& iterB)
    {
        return !iterA.equalsTo(iterB);
    }

    template<typename T>
    typename CycleArray<T>::const_iterator
    CycleArray<T>::begin() const
    {
        return const_array_iterator<T>(
            base_array_iterator<T>(const_cast<CycleArray<T>&>(*this), this->_front));
    }

    template<typename T>
    typename CycleArray<T>::const_iterator
    CycleArray<T>::end() const
    {
        return const_array_iterator<T>(
            base_array_iterator<T>(const_cast<CycleArray<T>&>(*this), this->_end));
    }

    template<typename T>
    typename CycleArray<T>::iterator
    CycleArray<T>::begin()
    {
        return array_iterator<T>(
            base_array_iterator<T>(*this, this->_front));
    }

    template<typename T>
    typename CycleArray<T>::iterator
    CycleArray<T>::end()
    {
        return array_iterator<T>(
            base_array_iterator<T>(*this, this->_end));
    }
}
